package a14_Sort;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author quan
 * @Description 非递归方式的快排
 * @Date 2023/4/28 16:01
 */
public class Demo3_QuickSortStack {
    public static void main(String[] args) {
        int[] arr = {1,56,23,4,12,9,6,8,17};
        quickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    /**
     * 非递归方式快排：借助栈。递归方式中的遍历看作二叉树的话是根左右，前序遍历，用栈实现。层序遍历用队列。
     * @param arr
     */
    public static void quickSort(int[] arr){
        //定义栈:先要弹出左边的l，因此先压右边的入栈
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length-1);
        stack.push(0);
        while (!stack.isEmpty()){
            int l = stack.pop();
            int r = stack.pop();
            if(l >= r){
                //当前这个子数组已经处理完毕，继续处理下一个子数组
                continue;
            }
            int p = partitionByHole(arr,l,r);
            //先将右半区间压入栈中
            stack.push(r);
            stack.push(p+1);
            //将左半区间压入栈中
            stack.push(p-1);
            stack.push(l);
        }
    }
    public static int partitionByHole(int[] arr, int l, int r) {
        //分区点为最左侧元素
        int pivot = arr[l];
        int i = l, j = r;
        while (i < j){
            //让j从右开始一直找到第一个小于pivot的值
            while (i < j && arr[j] > pivot){
                j--;
            }
            //此时j所指的元素是第一个小于pivot的值，将值赋值给i索引上的值
            arr[i] = arr[j];
            //此时从i开始向右找第一个大于pivot的值，放在j索引位置上
            while (i < j && arr[i] < pivot){
                i++;
            }
            //i找到了第一个大于pivot的值
            arr[j] = arr[i];
        }
        //此时i与j指向相同位置，回填分区点
        arr[j] = pivot;
        return j;
    }
}
